import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {

    /**
     * 数字 n 代表生成括号的对数，请你设计一个函数，
     * 用于能够生成所有可能的并且 有效的 括号组合。
     * @param n
     * @return
     */
    public List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if (n<=0)
            return ans;
        parenthesis("",n,n);
        return ans;

    }

    public void parenthesis(String str,int left,int right){
        if (left==0&&right==0)
        {
            ans.add(str);
            return;
        }
        if(left==right){
            parenthesis(str+"(",left-1,right);
        }else if (left>0){
            parenthesis(str+"(",left-1,right);
        }else {
            parenthesis(str+")",left,right-1);
        }

    }
}
